"""
题目：用递归求一个不含重复元素的数组的所有子集（如 [1,2] 的子集为 [[],[1],[2],[1,2]]）。
"""

def subsets(nums):
    """递归求数组的所有子集"""
    # 基线条件：空数组的子集只有空列表 空数组的子集只有空列表，这是递归的终止点，确保不会无限递归。
    if not nums:
        return [[]]
    # 取最后一个元素
    last = nums[-1]
    # 求剩余元素的所有子集 不包括last元素
    prev_subsets = subsets(nums[:-1])
    # 新子集 = 剩余元素的子集 + 剩余元素的子集都加上last元素
    #这是一个列表推导式：对 prev_subsets 中的每个子集 s，将 last 元素加入其中，生成新的子集。
    #例如，若 prev_subsets = [[], [1], [2], [1,2]]，last = 3，则 new_subsets = [[3], [1,3], [2,3], [1,2,3]]。
    new_subsets = [s + [last] for s in prev_subsets]
    #将 “剩余元素的子集”（prev_subsets）和 “包含最后一个元素的新子集”（new_subsets）合并，得到原数组的所有子集。 两类子集的并集就是原数组的所有子集，通过递归返回值的拼接即可得到最终结果。
    return prev_subsets + new_subsets
    #综上，这段代码通过递归将 “求原数组子集” 的问题分解为 “求剩余子数组子集” 和 “生成含最后元素的新子集” 两个子问题，最终合并结果得到所有子集；而递归的适用性正源于子集问题本身的可分解性和明确的终止条件。
# 测试
if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    # 输出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]